﻿#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
#include"Queue.h"


typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

//先序遍历
void PreOrder(BTNode* root);

//中序遍历
void InOrder(BTNode* root);

//后序遍历
void PostOrder(BTNode* root);

//二叉树节点个数
//想象成根节点+左子树+右子树的和，通过递归进行计算
int BinaryTreeSize(BTNode* root);

//二叉树叶子节点个数
//叶子节点的特点是左右节点为NULL
int BinaryTreeLeafSize(BTNode* root);

//二叉树第K层节点个数
//每递归一次K逐渐递减，当K=1就是对应层数，然后把左右子节点加起来
int BinaryTreeLevelKSize(BTNode* root, int k);

//二叉树的深度
//根节点 + Max(左子树，右子树)
int BinaryTreeDepth(BTNode* root);

// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

//二叉树的销毁
void BinaryTreeDestory(BTNode** root);

//层序遍历
//借助队列的数据结构取队头并处队头，把左右节点入队列
void LevelOrder(BTNode* root);

// 判断⼆叉树是否是完全⼆叉树
bool BinaryTreeComplete(BTNode* root);